package ListNode;

public class d230716 {
    // 删除有序链表中重复的元素-I
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            while (tmp != null && tmp.val == cur.val) {
                tmp = tmp.next;
            }
            cur.next = tmp;
            cur = cur.next;
        }
        return head;
    }

    // 删除有序链表中重复的元素-II
    public ListNode deleteDuplicates2 (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 创建一个链表头节点
        ListNode pHead = new ListNode(0);
        pHead.next = head;
        ListNode prev = pHead;  // 记录 cur 前一个位置
        ListNode cur = head;    // 遍历链表
        while (cur != null) {
            ListNode tmpCur = cur.next;     // 记录 cur 下一个位置
            boolean flag = false;           // 是否有重复

            while (tmpCur != null && tmpCur.val == cur.val) {
                // 有重复的数, 跳过, 知道不是重复的数
                tmpCur = tmpCur.next;
                flag = true;
            }

            if (flag) {
                // 删除重复的数
                prev.next = tmpCur;
                cur = tmpCur;
            } else {
                // 没出现重复的数, 两个正常往后移动一步
                prev = prev.next;
                cur = cur.next;
            }
        }
        return pHead.next;
    }
}
